﻿#include"global.h"
#include<memory>
#include"stdio.h"
Status InitMFSet(MFSet& S, int n);//构造由n个单元素子集构成的并查集S
Status CreateMFSet(MFSet& S, int* arr);//通过数组arr构造并查集（森林）
Status DestroyMFSet(MFSet& S);		//销毁并查集S
int FindMFSet(MFSet& S, int i);		//查找元素i在并查集中所属的子集，返回其代表元
Status DiffMFSet(MFSet& S, int i, int j);//判断i,j是否属于同一个子集，若是，返回true，否则返回false
Status UnionMFSet(MFSet& S, int i, int j);//合并并查集中元素i和j所属的两个子集
int main()
{
	MFSet S;
	InitMFSet(S,10);
	int arr[10] = { 8,-1,-1,1,1,2,3,2,-1,8 };
	CreateMFSet(S, arr);
	int result= FindMFSet(S, 6);
	printf("6所在树的代表元是%d\n", result);
	if (!DiffMFSet(S, 3, 0))
	{
		printf("结点3和0位于两棵不同树上\n");
	}
	UnionMFSet(S, 3, 0);
	if (DiffMFSet(S, 3, 0))
	{
		printf("合并后结点3和0位于同一棵树上\n");
	}
	DestroyMFSet(S);
	return 0;
}

Status InitMFSet(MFSet& S, int n)
{
	S.parent = (int*)malloc(n * sizeof(int));
	if (NULL == S.parent)return OVERFLOW;
	memset(S.parent, -1, n * sizeof(int));
	S.n = n;
	return SUCCESS;
}
Status CreateMFSet(MFSet& S, int* arr)
{
	if (S.n < 0||arr==NULL)return false;
	memcpy(S.parent, arr, sizeof(int) * S.n);
	return true;
}
Status DestroyMFSet(MFSet& S)
{
	if (S.parent != NULL)free(S.parent);
	S.n = 0;
	return SUCCESS;
}

int FindMFSet(MFSet& S, int i)
{
	if (i < 0 || i >= S.n)return -1;
	while (S.parent[i] >= 0)
	{
		i = S.parent[i];
	}
	return i;
}

Status DiffMFSet(MFSet& S, int i, int j)
{
	int ip=FindMFSet(S,i);
	int jp = FindMFSet(S, j);
	if (ip == jp)return true;
	else return false;
}

Status UnionMFSet(MFSet& S, int i, int j)//查找到根后将i所在的树合并到j所在的树上
{
	if (i >= S.n || j >= S.n || i < 0 || j < 0)return false;
	int ip=FindMFSet(S, i);
	int jp = FindMFSet(S, j);
	if (ip == jp)return false;//两个结点在同一颗树上也返回false
	S.parent[ip] = jp;
	return Status();
}
